package datastructures.stacks;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Design Note
 *
 * 1. Base data structure is array for the stack
 * 2. Stack is able to hold the generic type
 * 3. Size of stack
 *   1) The initial size of the stack is 100
 *   2) The size of stack will be doubled when the stack is full.
 *   3) The size of stack will be shrink when the number of elements in the stack is 25% of the size
 * 4. Exception
 *   1) Return null if the stack is empty when peek or pop is executed.
 *
 * @author Gatsby Lee
 *
 * @param <T>
 */

public class ArrayStack<T> implements StackADT<T> {

	private static final int DEFAULT_ARRAY_SIZE      = 100;
	private static final int RATE_TO_RESIZE_STACK    = 2;
	private static final double SHRINK_THESHHOLD_RATE_TO_RESIZE_STACK = 0.25;

	private int top;
	private T[] stack;

	public ArrayStack() {
		this(DEFAULT_ARRAY_SIZE);
	}

	public ArrayStack(int initialSize) {
		/*
		 *  We can't instantiate a generic type.
		 *  It means that we can't instantiate an array of a generic type
		 *  Therefore, we are instantiating an array of Objects and then
		 *  casting it as an array of our generic type.
		 */
		this.stack = (T[])(new Object[initialSize]);
		this.top = 0;
	}

	@Override
	public void push(T element) {
		if (this.stack.length == this.top) {
			resizeStack(this.stack.length * RATE_TO_RESIZE_STACK);
		}
		// use the index first and increment 'top'
		this.stack[this.top++] = element;
	}

	@Override
	public T pop() {

		// If the stack is empty, then return null
		if (this.top == 0) {
			return null;
		}

		// decrement 'top' first and use the index
		T element = (T)this.stack[--this.top];
		// reset the value in the index
		this.stack[this.top] = null;

		if (this.top > 0 && this.top == (int)(this.stack.length * SHRINK_THESHHOLD_RATE_TO_RESIZE_STACK)) {
			resizeStack(this.stack.length / RATE_TO_RESIZE_STACK);
		}

		return element;
	}

	@Override
	public T peek() {
		// If the stack is empty, then return null
		if (this.top == 0) {
			return null;
		}

		T element = (T)this.stack[this.top-1];
		return element;
	}

	@Override
	public boolean isEmpty() {
		if (this.top == 0) {
			return true;
		}
		return false;
	}

	@Override
	public int size() {
		return this.top;
	}

	/**
	 * Double the stack array size
	 */
	protected void resizeStack(int size) {
		T[] newStack = (T[])(new Object[size]);

		for (int i=0; i < this.top; i++) {
			newStack[i] = this.stack[i];
		}
		this.stack = newStack;
	}

	public Iterator<T> iterator() {
		return new ReverseArrayIterator();
	}

	private class ReverseArrayIterator implements Iterator<T> {

		private int topForIterator = top;

		@Override
		public boolean hasNext() {
			if (this.topForIterator == 0) {
				return false;
			}
			return true;
		}

		@Override
		public T next() {
			if (this.topForIterator == 0) {
				throw new NoSuchElementException();
			}
			return stack[--topForIterator];
		}

		/**
		 * This method is not supported
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}
}
